package com.dy.分类.数组._15_三数之和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
_15_三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
 */
/*
思路：

首先对数组从小到大排序，从一个数开始遍历，若该数大于0，后面的数不可能与其相加和为0，所以跳过；
否则该数可能是满足要求的第一个数，这样可以转化为求后面数组中两数之和为该数的相反数的问题。
定义两个指针一前一后，若找到两数之和满足条件则加入到解集中；若大于和则后指针向前移动，反之则前指针向后移动，
直到前指针大于等于后指针。这样遍历第一个数直到数组的倒数第3位。
注意再求和过程中首先判断该数字是否与前面数字重复，保证解集中没有重复解。
 */
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);
        if (nums.length < 3 || nums[0] > 0 || nums[nums.length - 1] < 0) return res;

        for (int i = 0; i < nums.length - 2; ) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int m = i + 1;
            int n = nums.length - 1;
            while (m < n) {
                if (nums[m] + nums[n] + nums[i] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[m]);
                    list.add(nums[n]);
                    res.add(list);
                    m++;
                    n--;
                    // 从左向右找第一个与之前处理的数不同的数的下标
                    while (m < n && nums[m] == nums[m - 1]) m++;
                    // 从右向左找第一个与之前处理的数不同的数的下标
                    while (m < n && nums[n] == nums[n + 1]) n--;
                } else if (nums[m] + nums[n] + nums[i] < 0) {
                    m++;
                    while (m < n && nums[m] == nums[m - 1]) m++;
                } else {
                    n--;
                    while (m < n && nums[n] == nums[n + 1]) n--;
                }

            }
            i++;
            // 从左向右找第一个与之前处理的数不同的数的下标
            while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
                i++;
            }

        }
        return res;
    }

    //复习
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //对数组排序
        Arrays.sort(nums);
        //如果元素小于3个，或者第一个大于0，最后一个小于0，返回
        if ((nums.length < 3) || (nums[0] > 0) || (nums[nums.length - 1]) < 0) {
            return list;
        }
        for (int i = 0; i < nums.length - 2; i++) {

            if (nums[i] > 0) {
                break;
            }
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                if (nums[i] + nums[start] + nums[end] == 0) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[start]);
                    tmp.add(nums[end]);
                    list.add(tmp);
                    //向前一步
                    start++;
                    end--;
                    //排除相同的
                    while (start < end && nums[start] == nums[start - 1]) {
                        start++;
                    }
                    while (end > start && nums[end] == nums[end + 1]) {
                        end--;
                    }
                } else if (nums[i] + nums[start] + nums[end] < 0) {
                    start++;
                } else if (nums[i] + nums[start] + nums[end] > 0) {
                    end--;
                }
            }


        }
        return list;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.threeSum2(new int[]{-1,0,1,2,-1,-4}));
    }
}
